One process replication approach in the UNIX family of operating systems (e.g. HP-UX, AIX and Solaris) involves copying the entire dynamic memory allocated portion (‘heap’) to the child process. Information about allocated (or used) and free blocks is retained in the child process. Comparable approaches are used in some other operating systems.
However, this approach has a number of disadvantages. The memory allocated in a parent process may not be required in the child process and—if it is not used by the child process—it must be explicitly freed in the child process if required elsewhere; the user must therefore keep track of all dynamically allocated memory chunks across the lifetime of an application and have the correct information available at the time of fork( ), so that the allocated memory is freed in the child process. Heap management algorithms, most of which use data structures termed “free lists”, are used to keep track of which parts of the memory are in use and which parts are free. In a free list, the free blocks are linked together in a list, typically ordered by starting addresses, with each node having information on the size of the memory available and the address of the memory location; the memory is considered as comprising a number of chunks, each with some size, as depicted schematically at 100 in FIG. 1. In FIG. 1, the blocks are numbers sequentially, free blocks are shown shaded, and used blocks are shown unshaded.
There may be two lists, one for used space, one for free. FIG. 2 depicts this arrangement schematically at 200 for the block usage shown in FIG. 1. In FIG. 2, the first field of each listed group of memory blocks 202, 204, 206, 208, 210 indicates whether the list is of used (U) or free (F) blocks; the second field indicates the address of the first block in a group of either used or free blocks and the third field indicates the number of blocks in that respective group. Thus, the upper register of FIG. 2 (comprising groups 202, 204 and 206) constitutes a first list (viz. of used memory blocks) 212 and the lower register (comprising groups 208 and 210) constitutes a second list (viz. of free memory blocks) 214.
Although these lists need not be ordered, in this example the contents of lists 212, 214 are ordered by block position. However, the lists may alternatively be ordered by size, as depicted schematically (also for the block usage shown in FIG. 1) at 300 in FIG. 3. In FIG. 3 list 302 of used blocks and list 304 of free blocks are ordered—from left to right—in order of increasing size of contiguous used and free chunks of memory, respectively.
In such implementations, a singly linked list of free memory chunks, called free list, is thus maintained (cf. free lists 214 and 304 of FIGS. 2 and 3 respectively). When a request to allocate memory is made, an appropriate chunk of free memory is found from the free list. How this chunk is found depends on the “fit policy.” Fit policies generally followed in existing systems are:
i) SEQUENTIAL FITS, including first fit, next fit, best fit, and worst fit;
ii) SEGREGATED FREE LISTS, including simple segregated storage and segregated fits;
iii) BUDDY SYSTEMS, including binary, weighted, and Fibonacci buddies, and double buddies;
iv) INDEXED FITS, which use structured indexes to implement a desired fit policy; and
v) BIT-MAPPED FITS, which are a particular kind of indexed fits.
Some existing implementations use Binning systems, where available chunks are maintained in bins that are grouped by size. This is usually implemented as a lookup table, comprising an array indexed by size, whose values are the numbers of the ranges. To look up which range a size falls into, the system indexes into the array and fetch the value stored there. When the memory is freed, that chunk of memory is allocated into the free list and may be taken and coalesced with its adjacent chunks in constant time, so that the memory chunk can be entered into the free list after coalescing.
In multi-threaded applications, the task of keeping track of memory allocation is even more complicated, owing to different threads of execution occurring at different times; some method of synchronization is required for handling the list of allocated blocks. This additional synchronization reduces the performance of all memory allocation and deallocation in the user application.
Furthermore, in multithreaded programs POSIX pthread_atfork( ) handlers are used to free memory in the child process. However, a race condition can arise between the fork happening in a forking thread and the time period between memory allocation and atfork handler registration in another thread.
Additionally, since there is no way to remove a registered atfork handler, a handler for freeing memory in a child process may lead to the freeing of dangling pointers if this particular memory chunk has already been released by the system. Each memory block has to be tracked by using a corresponding flag in the user application, which can lead to performance overheads in the application and duplicate book keeping with the memory allocator.